from typing import List


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        else:
            return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)

    def uniquePaths_dp(self, m: int, n: int) -> int:
        pass
        
    def uniquePaths_note(self, m: int, n: int) -> int:
        """ 
        note 可以优化， 一次记录一行或一列就可以推出下一行（列）
        而且可以直接用数组。。。
        """
        note = {}
        def helper(row, col):
            if row == 1 or col == 1:
                return 1
            else:
                try:
                    tmp = note[(row, col)]
                except:
                    tmp = helper(row-1, col) + helper(row, col-1)
                    note[(row, col)] = tmp
                return tmp
        return helper(m, n)


if __name__ == '__main__':
    s = Solution()
    print(s.uniquePaths_note(100, 100))
